//https://icoding.run/ide#/question/123
//树转二叉树

//使用队列，编写transfrom函数，将普通树转换成对应的二叉树。二叉树的相关定义如下：

typedef int DataType;

typedef struct Node{
    DataType data;
    struct Node* left;
    struct Node* right;
}BiTNode, *BiTree;
//普通树节点的定义如下：

#define MAX_CHILDREN_NUM 5
struct _CSNode
{
    DataType data;
    struct _CSNode *children[MAX_CHILDREN_NUM];
};
typedef struct _CSNode CSNode;
//其中，子树的根节点的指针存放在children数组的前k个元素中，即如果children[i]的值为NULL，而children[i-1]不为NULL，则表明该结点只有i棵子树，子树根结点分别保存在children[0]至children[i-1]中。

//队列相关定义及操作如下：

struct __Queue
{
    int i, j; //指向数组内元素的游标
    void **array;
};
typedef struct __Queue Queue;

Queue* create_queue(); //创建队列
bool is_empty_queue(Queue *tree); //队为空返回true,不为空时返回false
void* del_queue(Queue *tree); //结点指针出队
void add_queue(Queue *tree, void *node); //结点指针入队
void free_queue(Queue *tree); //释放队列
//transform函数定义如下：

BiTNode* transform(CSNode *root);
//其中 root 为普通树的根结点，函数返回该树对应二叉树的根结点。

#include <stdlib.h>
#include <stdio.h>
#include "bitree.h" //请不要删除，否则检查不通过

BiTNode* BuyNode(DataType x)
{
    BiTNode* newnode = (BiTNode*)malloc(sizeof(BiTNode));
    if(newnode == NULL)
    {
        exit(-1);
    }
    newnode->data = x;
    newnode->left = NULL;
    newnode->right = NULL;
    return newnode;
}

BiTNode* transform(CSNode *root){
    if (root == NULL) 
    {
        return NULL;
    }
    
    Queue* q = create_queue();
    BiTNode* retRoot = BuyNode(root->data);
    CSNode* CScur = NULL;
    BiTNode* Bicur = retRoot;
    add_queue(q, root);
    add_queue(q, retRoot);
    while(!is_empty_queue(q))
    {
        CScur = (CSNode*)del_queue(q);
        Bicur = (BiTNode*)del_queue(q);
        Bicur->left = BuyNode(CScur->children[0]->data);
        add_queue(q, CScur->children[0]);
        add_queue(q, Bicur->left);
        Bicur = Bicur->left;
        for(int i = 1; i < MAX_CHILDREN_NUM && CScur->children[i] != NULL; i++)
        {
            Bicur->right = BuyNode(CScur->children[i]->data);
            Bicur = Bicur->right;
            add_queue(q, CScur->children[i]);
            add_queue(q, Bicur);
        }
    }
    free_queue(q);
    return retRoot;
}